Virtual instructors are agents that provide natural language instructions to a
user in order to help him accomplish a task. These agents constitute a promising 
contribution to both education and entertainment. They can help a trainee
practice a task in a simulated training environment, for instance in military
training or medical training~\cite{kenny07,jan09}. They can also be used in video 
games~\cite{Millington06,dingum12}, where the purpose is to hae fun doing an \emph{a priori} unknown task. 
Currently, building an automated virtual instructor is a challenging and labor intensive
entreprise, and hence their use is not widespread. The goal of this paper is to help
making their development easier. 

% brief: applications of virtual instructors

A rapid method for developong virtual instructors would benefit three applications 
fields: video games and intelligent tutoring systems.

% brief: applications in video games

There are many examples of situations in video games in
which virtual instructors are needed. To begin with, most video games start with a small introduction, a tutorial, where the
player is instructed on how to move and what actions he can perform; a virtual instructor is needed to guide the player through this learning phase. Beyond the
purely didactic function of tutorials, virtual instructors are also needed
when the player has to collaborate with a non-player character to complete his goal. This is the
case in games like \emph{Call of Duty 4: Modern Warfare}\footnote{\emph{Call of Duty 4: Modern Warfare} was developed by
Infinity Ward, published by Activision, 2007.} where the player is a soldier and
can receive instructions by radio from his officer. In both cases, the
instructions are related to the physical world, and need to be uttered in real
time according to the player's actions. 
%LB: I removed this sentence because these intructions are not interactive
%Instructions are also present in all
%quest-based games, where the player receives some quest in the form of
%instructions (e.g. ``Fetch me ten bear skins'', ``Go see the archmage'', in games
%like \emph{Skyrim}\footnote{developed by Bethesda Game Studios, published by
%Bethesda Softworks, 2011.}). 
In general, for these applications, the instruction giver is
handcoded, using finite state machines~\cite{Millington06}. As a result, having a good or bad
instructor is still an art that depends on how good the state machine is at
faking some freedom (for instance, by foreseeing possible reactions of the
player) in order to make it more entertaining. 
%This approach is also difficult to
%implement since it is necessary to explicitely specify all states and transitions
%in order to link them to the appriate instructions. 
In this paper we propose a framework for rapid prototyping of virtual instructors, which uses an automated planner~\cite{nau04}
to select, at run, instructions that have been observed to take players closer the goal, from a similar state to the one the current player put himself into. 
% Moreover, it provides a method for
%automatically associating utterances to sequences of actions that intend to take
%the player closer to the goal. 
For a review of the use of other agent technologies (apart from natural language generation) used in games see~\cite{dingum12}. 

% brief: applications in intelligent tutoring systems

Currently, many simulations for
learning are built without mechanisms for guidance. As a result, these games rely
on discovery to achieve their pedagogical objectives. This approach which has been
shown to be ineffective for learners in new domains~\cite{}\fixme{Lu: Alex, which reference did you have in mind?}. To help address this
problem, there are several projects that attempt to build intelligent tutoring
systems in order to provide automated guidance in immersive learning
environments~\cite{Nkambou2010}. Currently building a tutoring system involves a substantial amount of
work and it is then an option only in situations in which they, in spite of their
relatively high development costs, still reduce the overall costs through
reducing the need for human instructors or sufficiently boosting overall
productivity. Such situations occur when large groups need to be tutored
simultaneously or when many replicated tutoring efforts are needed. Cases in
point are technical training situations such as training of military
recruits~\cite{Lane2009} or training mathematics~\cite{melis2005}. Our proposal provides
a methodology for rapidly prototyping intelligent tutors from corpora of
human-human interactions. Such corpora should be collected by
a real tutor (expert in the domain) and a small set of students.
In Section~\ref{sec:corpus} we discuss how the data collection has to be carried out.  
  
% brief: the complexity of virtual instructors

The complexity of building a virtual instructor relies building computational models that
give the agent the ability to decide: \emph{what} to say, and \emph{how} to say it. 
These abilities have to be good enough both to engage the trainee or 
the gamer in the activity and to help him solve the task successfully.

% brief: existing approaches

There are several existing approaches to modelling these two abilities. We briefly 
discuss here their advantages and disadvantages and, in this way, we motivate the need
for a new approach. 

% brief: industry approach

The most widespread approach in the game industry is to codify a script 
for the game story and trigger particular utterances at fixed poin ts of the script. 
This approach is usually implemented using finite state automata to keep track
of the current state of the script and to model loops~\cite{Millington06}. 
Its main advantage is that its implementation does not require specialized knowledge. However, it forces the player 
or trainee to follow a fixed script. Hence having a good or bad game is an art that depends on how good the script is at faking some freedom by foreseeing possible reactions of the player in order to make it more entertaining. 

% brief: symbolic nlg

A more flexible approach relies on \emph{symbolic natural language
generation} in which the sentences are not manually authored but
automatically generated thanks to grammars enriched with semantic information~\cite{reiter97,gardent07}. 
The advantage is a gain in flexibility because the utterances are produced during execution
depending on the current context of the interaction and do not need to be thought of in advance.
On the downside, the text generated by these methods is far from being natural as is the text obtained by
the industry approach. Furthermore this method requires labor intensive design and maintainance of the grammar and semantic resources.

% brief: statistical nlg

A more natural approach is \emph{statistical} generation that guide the natural language generation with the linguistic choices found in human-human corpora~\cite{Bangalore2000,foster08}. This approach achieves both flexibility and naturalness. However, to be effective, it requires an important amount of 
data manually annotated with linguistic information and, hence, are costly. 

% brief: generation by selection

Our contribution lies in the exploration and evaluation of a fourth approach, the
\emph{selection approach}. We acknowledge that, to really achieve the natural
extent of human sentences, we need to consider corpora of human interactions like
the statistical approach. However, we aim at removing the important cost of
manual annotation. Hence, the idea is not to generate a sentence by guiding
generation in a corpus but rather to \emph{directly select} the whole instruction
when we consider it is appropriate. The appropriateness of this decision must be
based on the corpus, that is how two human partners would provide instructions to
each other. 

% brief: our contribution

While the selection approach has already been used in purely
conversational systems such as negotiating agents~\cite{gandhe07}, question
answering characters~\cite{kenny07} or virtual partients~\cite{leuski09}, our
contribution lies in the adaptation of the selection approach to situated
task-oriented instructors. This context requires to face all the challenges that
are found in situated interaction such as dynamic environment in real time,
action and goal modelling, pragmatics linguistic phenomenas, etc. The key aspect
in the task-oriented selection is to model the actions in the planning paradigm
and to consider \emph{automatic annotation} of the corpus in terms of actions.
The virtual instructor is then able to select an instruction if he intends to
perform the actions that the instruction achieved in the corpus. We propose in
this paper task-oriented selection algorithms and their evaluation in the context
of the international challenge GIVE.

% paper summary

The paper is structured as follows: we first present in
Section~\ref{sec:previous-work} what do we mean by virtual instructors by looking
at the contexts in which they are necessary, and then detail the existing
approaches to their implementation, manual, classical and statistical. We present
next in Section~\ref{sec:corpus} the context of this work and the adjacent corpus
we collected. In Section~\ref{sec:algorithm}, we introduce the selection approach
for instruction giving by presenting the automatic annotation algorithm and the
instruction selection one. We then show the selection process at use on a
prototypical case in Section~\ref{sec:case-study}. Moreover, we present in
Section~\ref{sec:evaluation} the results of the GIVE evaluation in which we
tested the efficiency of the selection approach by comparing it to other
approaches. Finally, in Section~\ref{sec:discussion} we discuss how the
selection approach compares to the other approaches in terms of engineering
complexity, naturalness, and domain independence. Section~\ref{sec:conclusions}.  

